//输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 
//
// 
//
// 示例 1： 
//
// 
//输入：root = [3,9,20,null,null,15,7]
//输出：true 
//解释：如下图
// 
//
// 示例 2： 
//
// 
//输入：root = [1,2,2,3,3,null,null,4,4]
//输出：false
//解释：如下图
// 
//
// 
// 
//
// 提示： 
//
// 
// 0 <= 树的结点个数 <= 10000 
// 
//
// 注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/ 
//
// Related Topics 树 深度优先搜索 二叉树 👍 401 👎 0


package LeetCode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-05-17 15:07:56
 * @description LCR 176.判断是否为平衡二叉树
 */
public class PingHengErChaShuLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 PingHengErChaShuLcof fun=new PingHengErChaShuLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)

 // Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
     TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
         //当前树深度等于左右子树深度最大值+1
    //后序遍历+剪枝（从底至顶）
    public boolean isBalanced1(TreeNode root) {
        return dfs(root)!=-1;
    }
    //后序遍历树，如果不是平衡，直接返回
    //否则判断左右子树高度差，如果小于等于1
    //则返回当前节点的深度为左右最大+1，否则返回-1
    private int dfs(TreeNode node){
        if(node==null) return 0;
        int l=dfs(node.left);
        if(l==-1) return -1;
        int r=dfs(node.right);
        if(r==-1) return -1;
        return Math.abs(l-r)<2?Math.max(l,r)+1:-1;
    }
    //先序+判断深度（从顶至底）
    public boolean isBalanced2(TreeNode root) {
        if (root == null) return true;
        return Math.abs(depth(root.left) - depth(root.right)) <= 1 && isBalanced2(root.left) && isBalanced2(root.right);
    }

    private int depth(TreeNode root) {
        if (root == null) return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
    //记忆化搜索
    public boolean isBalanced(TreeNode root) {
        Map<TreeNode, Integer> memo = new HashMap<>(); // 存储节点的高度
        return checkBalanced(root, memo);
    }

    private boolean checkBalanced(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null) return true;

        // 检查左右子树是否平衡
        boolean leftBalanced = checkBalanced(root.left, memo);
        boolean rightBalanced = checkBalanced(root.right, memo);

        if (!leftBalanced || !rightBalanced) {
            return false; // 如果子树不平衡，整棵树也不平衡
        }

        // 计算左右子树高度（如果已缓存则直接取）
        int leftHeight = getHeight(root.left, memo);
        int rightHeight = getHeight(root.right, memo);

        // 判断当前树是否平衡
        return Math.abs(leftHeight - rightHeight) <= 1;
    }

    private int getHeight(TreeNode root, Map<TreeNode, Integer> memo) {
        if (root == null) return 0;
        if (memo.containsKey(root)) { // 如果已经计算过，直接返回
            return memo.get(root);
        }
        // 计算高度并缓存
        int height = Math.max(getHeight(root.left, memo), getHeight(root.right, memo)) + 1;
        memo.put(root, height);
        return height;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
